#include <vector>
#include <assert.h>
#include <stdio.h>
using namespace std;

int BinSearch(int* arr, int length, int start, int end)
{
    int result = 0;

    int m = (end - start) / 2;
    m = start + m;
    if(m - 1 >= 0 && m + 1 < length)
    {
        if(arr[m] < arr[m - 1] && arr[m] < arr[m+1])
        {
            result = arr[m];
        }
    }
    else if(m + 1 >= length) // 最右边元素
    {
        if(arr[m] < arr[m - 1]) result = arr[m];
    }
    
    if(result == 0 && m-1 >= start)
    {
        result = BinSearch(arr, length, start, m - 1);
    }
    if(result == 0 && m + 1 <= end)
    {
        result = BinSearch(arr, length, m + 1, end);
    }
    return result;
}

int MinOrder(int *arr, int length, int start, int end)
{
    int min = arr[start];
    for(int i = start + 1; i < end; ++i)
    {
        if(arr[i] < min) min = arr[i];
    }
    return min;
}

int minNumberInRotateArray(vector<int> rotateArray) {
    if(rotateArray.size() == 0) return 0;
    if(rotateArray.size() == 1) return rotateArray[0];
    int index1 = 0;
    int index2 = rotateArray.size() - 1;
    int mid = index1;
    while(rotateArray[index1] >= rotateArray[index2])
    {
        if(index2 - index1 == 1) return rotateArray[index2];
        mid = (index2 + index1) / 2;
        if(rotateArray[mid] == rotateArray[index1]) 
        {
            return MinOrder(&rotateArray[0], rotateArray.size(), index1, index2);
        }
        else if(rotateArray[mid] > rotateArray[index1]) 
        {
            index1 = mid;
        }
        else
        {
            index2 = mid;
        }
    }
    return rotateArray[mid];
}

int main()
{
    // 普通测试
    vector<int> arr = {3,4,5,1,2};
    int r = minNumberInRotateArray(arr);
    assert(r == 1);
    // 偶数元素测试
    arr = {3,4,1,2};
    r = minNumberInRotateArray(arr);
    // 左半序测试
    arr = {4,1,2,3};
    r = minNumberInRotateArray(arr);
    assert(r == 1);
    // 单元素测试
    arr = {1};
    r = minNumberInRotateArray(arr);
    assert(r == 1);
    // 边缘测试
    arr = {1,2,3};
    r = minNumberInRotateArray(arr);
    assert(r == 1);
    arr = {3,4,5,1};
    r = minNumberInRotateArray(arr);
    assert(r == 1);
    arr = {2,1,2,2,2};
    r = minNumberInRotateArray(arr);
    assert(r == 1);

    // 没有元素测试
    arr = {};
    r = minNumberInRotateArray(arr);
    assert(r == 0);

    return 0;
}